public class 最长上升子子序列_贪心二分 {
    public int LIS (int[] a) {
        //创建一个数组来存储元素
        int[] arr = new int[100001];
        //标记长度
        int size = -1;
        int n = a.length;

        for(int i = 0;i < n;i++){
            //开始为空直接添加
            if(size == -1){
                arr[++size] = a[i];
                continue;
            }
            //判断大小, 比最大的大直接加, 没有用二分找出左边界>=
            if(arr[size] < a[i]){
                arr[++size] = a[i];
            }else{
                int index = find(arr,a[i],size);
                arr[index] = a[i];
            }
        }
        //长度返回要加一
        return size + 1;
    }

    private int find(int[] arr,int target,int right){
        int left = 0;
        while(left < right){
            int mid = (left + right) / 2;
            if(arr[mid] >= target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}
